package com.algrithom.graph.toposort;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Stack;

import com.common.model.AdjacentEdge;
import com.common.model.AdjacentTable;

public class AoePlan {
    
    public static void main(String[] args){
        List<AdjacentTable> adjacentTables = createTopoGraph();
        topoSort(adjacentTables);
    }
    
    private static List<AdjacentTable> createTopoGraph(){
        List<AdjacentTable> list = new ArrayList<>();
        AdjacentTable adjacentTable = new AdjacentTable();
        adjacentTable.setIndegree(0);
        adjacentTable.setNumber(1);
        AdjacentEdge adjacentEdge = new AdjacentEdge();
        adjacentEdge.setNumber(3);
        adjacentTable.setNext(adjacentEdge);
        list.add(adjacentTable);
        
        adjacentTable = new AdjacentTable();
        adjacentTable.setIndegree(0);
        adjacentTable.setNumber(2);
        adjacentEdge = new AdjacentEdge();
        adjacentEdge.setNumber(3);
        adjacentTable.setNext(adjacentEdge);
        list.add(adjacentTable);
        
        adjacentTable = new AdjacentTable();
        adjacentTable.setIndegree(2);
        adjacentTable.setNumber(3);
        adjacentEdge = new AdjacentEdge();
        adjacentEdge.setNumber(4);
        AdjacentEdge next = new AdjacentEdge();
        next.setNumber(5);
        adjacentEdge.setNext(next);
        adjacentTable.setNext(adjacentEdge);
        list.add(adjacentTable);
        
        adjacentTable = new AdjacentTable();
        adjacentTable.setIndegree(1);
        adjacentTable.setNumber(4);
        adjacentEdge = new AdjacentEdge();
        adjacentEdge.setNumber(5);
        adjacentTable.setNext(adjacentEdge);
        list.add(adjacentTable);
        
        adjacentTable = new AdjacentTable();
        adjacentTable.setIndegree(2);
        adjacentTable.setNumber(5);
        list.add(adjacentTable);
        return list;
    }
    
    private static void topoSort(List<AdjacentTable> adjacentTables){
        Stack<Integer> stack = new Stack<>();
        Map<Integer,AdjacentTable> map = new HashMap<>();
        adjacentTables.forEach(adjacentTable -> {
            if (adjacentTable.getIndegree() == 0) {
                stack.push(adjacentTable.getNumber());
            }
            map.put(adjacentTable.getNumber(),adjacentTable);
        });
        while (!stack.empty()) {
            int index = stack.pop();
            System.out.println("TopoSort is: " + index + " ");
            AdjacentEdge adjacentEdge = map.get(index).getNext();
            while (Objects.nonNull(adjacentEdge)) {
                AdjacentTable adjacentTable = map.get(adjacentEdge.getNumber());
                int indegree = adjacentTable.getIndegree() - 1;
                adjacentTable.setIndegree(indegree);
                if (indegree == 0) {
                    stack.push(adjacentTable.getNumber());
                }
                adjacentEdge = adjacentEdge.getNext();
            }
        }
    }
}
